// https://leetcode.cn/problems/word-ladder/

// 题干：字典 wordList 中从单词 beginWord 和 endWord 的 转换序列
//      是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：
//      每一对相邻的单词只差一个字母。
//      对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
//      sk == endWord
//      给你两个单词 beginWord 和 endWord 和一个字典 wordList ，
//      返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

// 示例：输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
//      输出：5

// 碎语：同最小基因序列一样，唯一不同的是算上单词数目，包括了起始位置

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList)
    {
        unordered_set<string> vis; // 标记已经记录过的字符串
        unordered_set<string> hash(wordList.begin(), wordList.end()); // 标记wordList里面的合法字符串
        string change = "abcdefghijklmnopqrstuvwxyz";

        if (beginWord == endWord) return 1;
        if (!hash.count(endWord)) return 0;

        queue<string> q;
        q.push(beginWord);
        vis.insert(beginWord);

        int ret = 1, len = beginWord.size();
        while (q.size()){
            ret++; // 每次拓展都+1
            int sz = q.size();

            while (sz--){
                auto t = q.front();
                q.pop();

                for (int i = 0 ; i < len ; i++){
                    string tmp = t;
                    for (int j = 0 ; j < 26 ; j++){
                        tmp[i] = change[j];
                        if (hash.count(tmp) && !vis.count(tmp)){
                            if (tmp == endWord) return ret;
                            vis.insert(tmp);
                            q.push(tmp);
                        }
                    }
                }
            }
        }

        return 0;
    }
};

int main()
{
    Solution sol;
    string beginWord = "red", endWord = "tax";
    vector<string> wordList = {"ted","tex","red","tax","tad","den","rex","pee"};

    cout << sol.ladderLength(beginWord, endWord, wordList) << endl;

    return 0;
}